package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description
 * @date 2025/4/27 14:25
 */
public class ConvertBST_538 {

    int sum = 0;
    public TreeNode convertBST2(TreeNode root) {
        dfs2(root);
        return root;
    }

    // 按右中左顺序遍历，累加即可
    public void dfs2(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs2(root.right);

        sum += root.val;
        root.val = sum;

        dfs2(root.left);
    }

    /**
     * 参考dmsxl
     * <p>
     * 思路：
     * BST的中序遍历是升序数组，BST转化为题目要求的累加树，相当于对一个严格升序的数组，从后往前（从最大元素到最小元素），进行累加操作。
     * 对于数组从后往前累加，很容易想到双指针，移动时更新cur的最新累加值；同理，BST也可以这样做。
     * 而一棵BST，想要从最大的元素开始倒过来累加，中序：左中右，是先访问最小元素，那倒过来 右中左，就可以先访问最大元素。
     */
    TreeNode pre = null;

    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;

        // 右
        convertBST(node.right);

        // 中
        int sum = pre == null ? 0 : pre.val;
        node.val += sum;
        pre = node;

        // 左
        convertBST(node.left);
    }

}
